package leetcode;

import leetcode.Hot100.maxDepth;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Cheng Jun
 * Description: 根据二叉树数组，构建一棵二叉树。通过 LeetCode 关于树的问题给出的测试案例 构建二叉树用于本地调试
 * @version 1.0
 * @date 2021/12/13 9:09
 */
public class TreeNodeUtil {

    public static void main(String[] args) {
        System.out.println(getBT(new Object[]{1, 2, 3, 4, 5, null, 7}));
        System.out.println(getBTByIter(new Object[]{1, 2, 3, 4, 5, null, 7}));
        System.out.println(getBTByRec(new Object[]{1, 2, 3, 4, 5, null, 7}));
    }

    /**
     * 根据二叉树数组构建 二叉树
     *
     * @param valArray 以二叉树 形式给出，节点不存在的 为 null
     * @return leetcode.TreeNode
     * @author Cheng Jun
     * @date 2021/12/13 9:12
     */
    public static TreeNode getBT(Object[] valArray) {
        int length = valArray.length;
        // 空树
        if (length == 0) return null;
        TreeNode[] valTreeNode = new TreeNode[length];
        // 创建 TreeNode数组
        for (int i = 0; i < length; i++) {
            if (valArray[i] != null) valTreeNode[i] = new TreeNode(Integer.valueOf(valArray[i].toString()));
            else valTreeNode[i] = null;
        }
        // 完善数组的的 左右子节点
        for (int i = 0; i < length; i++) {
            if (2 * i + 1 < length && valTreeNode[i] != null) valTreeNode[i].left = valTreeNode[2 * i + 1];
            if (2 * i + 2 < length && valTreeNode[i] != null) valTreeNode[i].right = valTreeNode[2 * i + 2];
        }
        return valTreeNode[0];
    }

    /**
     * 优化 getBT，一次倒序循环
     * iteration
     *
     * @param valArray
     * @return leetcode.TreeNode
     * @author Cheng Jun
     * @date 2021/12/13 9:34
     */
    public static TreeNode getBTByIter(Object[] valArray) {
        int length = valArray.length;
        // 空树
        if (length == 0) return null;
        TreeNode[] valTreeNode = new TreeNode[length];
        for (int i = length - 1; i >= 0; i--) {
            if (valArray[i] != null) {
                valTreeNode[i] = new TreeNode(Integer.valueOf(valArray[i].toString()));
                if (2 * i + 1 < length) valTreeNode[i].left = valTreeNode[2 * i + 1];
                if (2 * i + 2 < length) valTreeNode[i].right = valTreeNode[2 * i + 2];
            } else {
                valTreeNode[i] = null;
            }
        }
        return valTreeNode[0];
    }

    /**
     * 递归实现 根据二叉树数组构建 二叉树
     *
     * @param valArray
     * @return leetcode.TreeNode
     * @author Cheng Jun
     * @date 2021/12/13 9:45
     */
    public static TreeNode getBTByRec(Object[] valArray) {
        int length = valArray.length;
        // 空树
        if (length == 0) return null;
        return getChildNode(valArray, 0);
    }

    /**
     * 递归实现构造节点的左右子节点
     *
     * @param valArray
     * @param nodeIndex
     * @return leetcode.TreeNode
     * @author Cheng Jun
     * @date 2021/12/13 9:45
     */
    private static TreeNode getChildNode(Object[] valArray, int nodeIndex) {
        if (nodeIndex < valArray.length && valArray[nodeIndex] != null) {
            TreeNode treeNode = new TreeNode(Integer.valueOf(valArray[nodeIndex].toString()));
            // 递归获取 左节点、右节点
            TreeNode leftChildNode = getChildNode(valArray, 2 * nodeIndex + 1);
            TreeNode rightChildNode = getChildNode(valArray, 2 * nodeIndex + 2);
            treeNode.left = leftChildNode;
            treeNode.right = rightChildNode;
            return treeNode;
        } else {
            return null;
        }
    }
}
